{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #找到第 k 位数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKthNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到第 k 位数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某班级学号记录系统发生错乱，原整数学号序列 <code>[0,1,2,3,4,...]</code> 分隔符丢失后变为 <code>01234...</code> 的字符序列。请实现一个函数返回该字符序列中的第 <code>k</code> 位数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 5\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 12\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>第 12 位数字在序列 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 1 ，它是 11 的一部分。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= k &lt;&nbsp;2<sup>31</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 400 题相同：<a href=\"https://leetcode-cn.com/problems/nth-digit/\">https://leetcode-cn.com/problems/nth-digit/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof](https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof](https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '12']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit = 1\n",
    "        start = 1\n",
    "        count = 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            digit += 1\n",
    "            start *=10\n",
    "            count = 9 * digit * start\n",
    "        num = start + (k - 1) // digit\n",
    "        return int(str(num)[(k-1)%digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        n = 0\n",
    "        t = 0\n",
    "        last = 0\n",
    "        while t < k:\n",
    "            n += 1\n",
    "            last = t + 1\n",
    "            t += n*9*(10**(n-1))\n",
    "        # print(n, last, t)\n",
    "        if n == 1:\n",
    "            return k\n",
    "        else:\n",
    "            num = (k-last)//n + 10**(n-1)\n",
    "            idx = (k-last)%n\n",
    "            # print(num, idx)\n",
    "            return int(str(num)[idx])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 0\n",
    "        start_length = 0\n",
    "        end_length = 0\n",
    "        while True:\n",
    "            start_index = 0 if i == 0 else 10 ** i\n",
    "            end_index = 0\n",
    "            for j in range(i + 1):\n",
    "                end_index += 9 * 10 ** j\n",
    "            start_length = end_length\n",
    "            end_length += ((end_index - start_index + 1) * (i + 1))\n",
    "            if end_length >= k:\n",
    "                l = k - start_length\n",
    "                value = str(start_index + l // (i + 1))\n",
    "                return int(value[l % (i + 1)])\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        lower = 0\n",
    "        upper = 9\n",
    "        digi_base = 0\n",
    "        digi_length = 1\n",
    "\n",
    "        while k > upper:            \n",
    "            # print(f'lower:{lower} upper:{upper} digi_length:{digi_length} digi_base:{digi_base}')\n",
    "            digi_base = digi_base * 10 if digi_base > 0 else 10\n",
    "            digi_length += 1\n",
    "            lower = upper + 1\n",
    "            upper += digi_base * 9 * digi_length\n",
    "        \n",
    "        num = (k - lower) // digi_length + digi_base\n",
    "        pos = (k - lower) % digi_length\n",
    "\n",
    "        # print(f'Found lower:{lower} upper:{upper} digi_length:{digi_length} digi_base:{digi_base} number:{num} pos:{pos}')        \n",
    "\n",
    "        return num // (10 ** (digi_length - pos - 1)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        n = 1\n",
    "        s = 10\n",
    "        while True:\n",
    "            if k < s:\n",
    "                if n > 1: k -= (s - 9*10**(n-1)*n)\n",
    "                b, d = divmod(k, n)\n",
    "                start = 0 if n == 1 else 10**(n-1)\n",
    "                return int(str(start + b)[d])\n",
    "            n += 1\n",
    "            s += 9*10**(n-1)*n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit\n",
    "        return int(str(num)[(k - 1) % digit])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit,start,count = 1,1,9\n",
    "        while k>count:\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9*start*digit\n",
    "        if k%digit == 0:\n",
    "            x = k//digit\n",
    "        else:\n",
    "            x = k//digit+1\n",
    "        num = start + x - 1\n",
    "        num = str(num)\n",
    "        return int(num[k%digit-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        # 初始化从一位数开始\n",
    "        digit, start, count = 1, 1, 9\n",
    "\n",
    "        # 1.确定所求数位的所在数字 num 的位数 digit\n",
    "        while k > count: \n",
    "            k -= count # 循环减去 digit 对应的数位数量 count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "\n",
    "        # 2.确定所求数位所在的数字 num\n",
    "        num = start + (k - 1) // digit # start 为第 0 个数字\n",
    "\n",
    "        # 3.确定所求数位在 num 的哪一数位\n",
    "        # 先转为 string，根据索引获得该位数字字符，最后转化为 int\n",
    "        return int(str(num)[(k - 1) % digit]) # 数字的首个数位为第 0 位\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 1\n",
    "        while i * (10 ** i) < k:\n",
    "            k += 10 ** i \n",
    "            i += 1\n",
    "        return int(str(k // i)[k % i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k-1)//digit\n",
    "        return int(str(num)[(k-1)%digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 1\n",
    "        while i * (10 ** i) < k:\n",
    "            k += 10 ** i\n",
    "            i += 1\n",
    "        return int(str(k // i)[k % i]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int) -> int:\n",
    "        base = 1\n",
    "        numDigits = 1\n",
    "        while n > 9 * numDigits * base:\n",
    "            n -= 9 * numDigits * base\n",
    "            numDigits += 1\n",
    "            base *= 10\n",
    "        q, r = divmod(n - 1, numDigits)\n",
    "        return int(str(base + q)[r])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit=1\n",
    "        count=9\n",
    "        start=1\n",
    "        while k>count:\n",
    "            k-=count\n",
    "            digit+=1\n",
    "            start*=10\n",
    "            count=digit*start*9 \n",
    "        n=(k-1)//digit\n",
    "        inn=(k-1)%digit\n",
    "        num=start+n\n",
    "        return int(str(num)[inn])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        if k < 10: return k\n",
    "        pre = 10\n",
    "        for i in range(2, 11):\n",
    "            s = 10**(i - 1)\n",
    "            gap = (int('9'*i) - s + 1) * i\n",
    "            count = k - pre\n",
    "\n",
    "            print(i, gap)\n",
    "\n",
    "            if gap >= count:\n",
    "\n",
    "                mul, rest = count // i, count % i\n",
    "                \n",
    "                print(i, s, pre, '-> ',count, mul , '-> ', s + mul, rest)\n",
    "\n",
    "                return int(str(s + mul)[rest])\n",
    "\n",
    "            pre += gap\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit = 1\n",
    "        start = 1\n",
    "        cnt = 9\n",
    "        while k > cnt:\n",
    "            k -= cnt\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            cnt = 9 * digit * start\n",
    "        num = start + (k-1)//digit\n",
    "        return int(str(num)[(k-1)%digit])\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        lower = 0\n",
    "        upper = 9\n",
    "        digi_base = 0\n",
    "        digi_length = 1\n",
    "\n",
    "        while k > upper:            \n",
    "            # print(f'lower:{lower} upper:{upper} digi_length:{digi_length} digi_base:{digi_base}')\n",
    "            digi_base = digi_base * 10 if digi_base > 0 else 10\n",
    "            digi_length += 1\n",
    "            lower = upper + 1\n",
    "            upper += digi_base * 9 * digi_length\n",
    "        \n",
    "        num = (k - lower) // digi_length + digi_base\n",
    "        pos = (k - lower) % digi_length\n",
    "\n",
    "        # print(f'Found lower:{lower} upper:{upper} digi_length:{digi_length} digi_base:{digi_base} number:{num} pos:{pos}')        \n",
    "\n",
    "        return num // (10 ** (digi_length - pos - 1)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        # 首先判断target是几位数，用digits表示\n",
    "        base = 9\n",
    "        digits = 1\n",
    "        while k - base * digits > 0:\n",
    "            k -= base * digits\n",
    "            base *= 10\n",
    "            digits += 1\n",
    "        # 计算target的值\n",
    "        idx = k % digits  # 注意由于上面的计算，k现在表示digits位数的第k个数字\n",
    "        if idx == 0: \n",
    "            idx = digits\n",
    "        number = 1\n",
    "        for i in range(1,digits):\n",
    "            number *= 10\n",
    "        if idx == digits:\n",
    "            number += k // digits - 1\n",
    "        else:\n",
    "            number += k // digits\n",
    "        # 找到target中对应的数字\n",
    "        for i in range(idx,digits):\n",
    "            number //= 10\n",
    "        return number % 10\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 1\n",
    "        while i * (10 ** i) < k:\n",
    "            k += 10 ** i \n",
    "            i += 1\n",
    "        return int(str(k // i)[k % i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n = n - count\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            count = 9 * start * digit\n",
    "\n",
    "        num = start + (n - 1) // digit\n",
    "        return int(str(num)[(n-1) % digit])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        if k>=1 and k<=9:\n",
    "            return k \n",
    "        \n",
    "        num = 1\n",
    "        base = 1\n",
    "        cnt = 9 * base * num\n",
    "        while k > cnt + 9 * (base*10) * (num+1):\n",
    "            cnt += 9 * (base*10) * (num+1)\n",
    "            base *= 10\n",
    "            num += 1\n",
    "        \n",
    "        diff = k - cnt\n",
    "        if diff==0:\n",
    "            return 9\n",
    "        else:\n",
    "            if diff%(num+1)==0:\n",
    "                return (10**num + diff//(num+1)-1)%10\n",
    "            else:\n",
    "                c = 10**num + diff//(num+1)\n",
    "                tlist = []\n",
    "                while c>0:\n",
    "                    tlist = [c%10] + tlist\n",
    "                    c //= 10\n",
    "                return tlist[diff%(num+1)-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- encoding: utf-8 -*-\n",
    "# @Author  :   Liang Hao \n",
    "# @Time    :   2023/11/10 14:48:52\n",
    "# @File    :   LCR_163.py\n",
    "# @Contact   :   lianghao@whu.edu.cn\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n):\n",
    "        \"\"\"\n",
    "        1~9: 9\n",
    "        10 ~ 99: 90\n",
    "        100 ~ 999 : 900\n",
    "        count = base * digit * 9\n",
    "        \"\"\"\n",
    "        digit, base = 1, 1\n",
    "        \n",
    "        while n > 9 * base * digit:\n",
    "            n = n - 9 * base * digit\n",
    "            base = base * 10\n",
    "            digit = digit + 1\n",
    "        \n",
    "        # 此时 n < 9 * base * digit， 假设base=100，\n",
    "        # 说明n是100~999中的某个数\n",
    "        # 找到这个数\n",
    "        val = base + (n - 1) // digit\n",
    "        # 找到第几位数\n",
    "        index = (n - 1) % digit\n",
    "        \n",
    "        return int(str(val)[index])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 1\n",
    "        while i * (10 ** i) < k:\n",
    "            k += 10 ** i\n",
    "            i += 1\n",
    "        return int(str(k // i)[k % i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        k -= 1\n",
    "        nd = 1\n",
    "        start = 1\n",
    "        cnt = 9\n",
    "        while k > cnt:\n",
    "            k -= cnt\n",
    "            start *= 10\n",
    "            nd += 1\n",
    "            cnt = 9 * start * nd\n",
    "        num = start + k // nd\n",
    "        return int(str(num)[k % nd])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 1\n",
    "        while i * (10 ** i) < k:\n",
    "            k += 10 ** i\n",
    "            i += 1\n",
    "        return int(str(k // i)[k % i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 1\n",
    "        while i * (10 ** i) < k:\n",
    "            k += 10 ** i\n",
    "            i += 1\n",
    "        return int(str(k // i)[k % i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1  \n",
    "            count = 9 * start * digit \n",
    "        num = start + (k - 1) // digit\n",
    "        return int(str(num)[(k - 1) % digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit=1\n",
    "        count=9\n",
    "        start=1\n",
    "        while k>count:\n",
    "            k-=count\n",
    "            digit+=1\n",
    "            start*=10\n",
    "            count=digit*start*9 \n",
    "        n=(k-1)//digit\n",
    "        inn=(k-1)%digit\n",
    "        num=start+n\n",
    "        return int(str(num)[inn])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            digit += 1 \n",
    "            start *= 10\n",
    "            count= 9 * start * digit \n",
    "        \n",
    "        num = start + (k - 1) // digit  #确定数字\n",
    "        n = (k - 1) % digit #第n位数\n",
    "        return int(str(num)[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int) -> int:\n",
    "        # 位数（一位数，两位数...）\n",
    "        digit = 1\n",
    "        # 1,10,100, 1000 这样的后缀\n",
    "        base = 1\n",
    "\n",
    "        while n > 9 * base * digit:\n",
    "            n -= 9 * base * digit\n",
    "            base *= 10\n",
    "            digit += 1\n",
    "\n",
    "        # 此时假设 base = 1000，那么说明 n 是 100~999 中的某个三位数的某一位\n",
    "        # 哪个三位数呢？这样算：\n",
    "        val = base + (n - 1) // digit\n",
    "\n",
    "        # 是这个三位数的第几位呢？这样算：\n",
    "        index = (n - 1) % digit\n",
    "        print(val, index)\n",
    "        # 怎么把 val 的第 index 这一位数字抠出来呢？可以转化成字符串来算：\n",
    "        return int(str(val)[index])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count: # 1.\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (n - 1) // digit # 2.\n",
    "        return int(str(num)[(n - 1) % digit]) # 3.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            digit += 1 \n",
    "            start *= 10\n",
    "            count= 9 * start * digit \n",
    "        \n",
    "        num = start + (k - 1) // digit  #确定数字\n",
    "        n = (k - 1) % digit #第n位数\n",
    "        return int(str(num)[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int):\n",
    "        start, digit, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = str(start + (n-1) // digit)\n",
    "        res = num[(n-1) % digit]\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * digit * start\n",
    "        num = start + (k-1) // digit\n",
    "        return int(str(num)[(k-1)%digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k):\n",
    "        if k <= 9:\n",
    "            return k\n",
    "        idx = 2\n",
    "        c = 9\n",
    "        while True:\n",
    "            start = c + 1\n",
    "            end = idx * (10**idx - 1 - 10**(idx-1) + 1) + start - 1\n",
    "            if k > end:\n",
    "                c = end\n",
    "                idx += 1\n",
    "                continue\n",
    "            temp = k - start + 1\n",
    "            temp1 = temp // idx\n",
    "            temp2 = temp % idx\n",
    "            if temp2 != 0:\n",
    "                temp1 = 10**(idx-1) + temp1\n",
    "                return int(str(temp1)[temp2-1])\n",
    "            else:\n",
    "                temp1 = 10**(idx-1) + temp1 - 1\n",
    "                return int(str(temp1)[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "# 0 只占1为， 1个\n",
    "# 1~9 只占 1 位, 共 9 个\n",
    "# 10~99 占 2 位, 共 90 个\n",
    "# 100~999 占 3 位, 共 900 个\n",
    "# 1000~9999 占 4 位, 共 9000 个\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            start *= 10 # 1, 10, 100, ...\n",
    "            digit += 1  # 1,  2,  3, ...\n",
    "            count = 9 * start * digit # 9, 180, 2700, ...\n",
    "\n",
    "\n",
    "        num_num = start + (k-1) // digit\n",
    "        num_dig = (k-1) % digit\n",
    "        # if digit == 1:\n",
    "        #     res = str(num_num)\n",
    "        # else:\n",
    "        res = str(num_num)\n",
    "        return int(res[num_dig])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int) -> int:\n",
    "        if n<10:return n\n",
    "        s = str(n)\n",
    "        l = math.pow(10,len(s)-1)\n",
    "        left = 0\n",
    "        i=1\n",
    "        while i<len(s):\n",
    "            left+= 10 if i==1 else i*(math.pow(10,i)-math.pow(10,i-1))\n",
    "            if n<left:\n",
    "                left-=i*(math.pow(10,i)-math.pow(10,i-1))\n",
    "                break\n",
    "            i+=1\n",
    "        hh = (n-left)\n",
    "        a = str(hh//i+math.pow(10,i-1))\n",
    "        return int(a[int(hh%i)])\n",
    "# 0:1\n",
    "# 1-9:9\n",
    "# 10-99:90\n",
    "# 100-999:900\n",
    "# 1000-9999:9000\n",
    "# 10000-99999:90000\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k > count: # 1.\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit # 2.\n",
    "        return int(str(num)[(k - 1) % digit]) # 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "\n",
    "        num = start + (k - 1) // digit\n",
    "        return int(str(num)[(k - 1) % digit])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        i = 1\n",
    "        while i * (10 ** i) < k:\n",
    "            k += 10 ** i\n",
    "            i += 1\n",
    "        return int(str(k//i)[k%i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "\n",
    "        digit, start, count = 1, 1, 9\n",
    "\n",
    "        while k > count:\n",
    "            k -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (k - 1) // digit\n",
    "        return int(str(num)[(k - 1) % digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        def bs(cur: int) -> int:\n",
    "            cnt = 0\n",
    "            n = len(str(cur))\n",
    "            for i in range(1, n):\n",
    "                cnt += 10 ** (i - 1) * 9 * i\n",
    "            cnt += (cur - 10 ** (n - 1) + 1) * n\n",
    "            return cnt\n",
    "        left, right = 0, k\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            res = bs(mid)\n",
    "            if res == k:\n",
    "                return mid % 10\n",
    "            if res > k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return int(str(left)[k-bs(left-1)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        start,digit,count=1,1,9\n",
    "        while k > count:\n",
    "            k-=count\n",
    "            start*=10\n",
    "            digit+=1\n",
    "            count=9*start*digit\n",
    "        m=start+(k-1)//digit\n",
    "        return int(str(m)[(k-1)%digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        1位数有10个\n",
    "        2位数有9*10\n",
    "        3位数有9*10*10\n",
    "        因此我们确定它是几位数 然后是第几个 最后确定第几位\n",
    "        假如n是200，那么我们就知道它一定是三位数，且它是三位数里的第200−9-180=11转换成从0开始的坐标就是11-1=10 \n",
    "        三位数是每三位一个数，那么它就是三位数里的10//3=3 也就是103了 余下1 那么就是第一位 也就是0\n",
    "        \"\"\"\n",
    "        bit,base = 1,9 # 位数和个数\n",
    "        while n > bit*base:\n",
    "            n -= bit*base\n",
    "            bit += 1\n",
    "            base *= 10\n",
    "        n -= 1 # 从0开始\n",
    "        #定位到目标数字\n",
    "        num = 10**(bit-1)+n//bit\n",
    "        #定位到目标位数\n",
    "        id = n % bit\n",
    "        return num // (10 ** (bit - 1 - id)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while k>count:\n",
    "            k -= count\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            count = 9*start*digit\n",
    "        num = start + (k-1) // digit\n",
    "        # retrun int(str(num)[(k-1) % digit])\n",
    "        return int(str(num)[(k - 1) % digit])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, k: int) -> int:\n",
    "        count = 9\n",
    "        start = 1\n",
    "        digit = 1\n",
    "        while (k>count):\n",
    "            k-=count\n",
    "            start *=10\n",
    "            digit +=1\n",
    "            count = 9*start*digit\n",
    "\n",
    "        num = start+(k-1)//digit\n",
    "        d = str(num)[(k-1)%digit]\n",
    "\n",
    "        return int(d)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
